package main

import "fmt"

func main() {
	var h []int
	h = []int{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1}
	v := trap2(h)
	fmt.Println(v)
}

// 单调栈实现
// 如果新元素比栈顶大，入栈
// 否则栈内元素出栈 一直到比栈顶小的元素

// 单调栈的特点 以递增为例
// 1.栈内元素递增
// 2.当需要出栈时，要出来的元素前后都是比自己小的元素

// 43 接雨水 https://leetcode.cn/problems/trapping-rain-water
func trap(height []int) int {
	stack := []int{}

	ans := 0
	for i, h := range height {
		//结算 直到栈为空或者栈顶>当前元素； 结算 并 入栈
		for len(stack) != 0 && height[stack[len(stack)-1]] < h {
			//栈顶的索引和高度
			peakIndex := stack[len(stack)-1]
			peekH := height[peakIndex]

			//弹出栈顶元素
			stack = stack[:len(stack)-1]
			if len(stack) == 0 {
				break // 栈空了 没法接
			}

			// 走到这里说明stack不为空 说明后面一定 >= 弹出的元素
			leftIndex := stack[len(stack)-1]
			leftHeight := height[leftIndex]
			tmpH := min(leftHeight, h) - peekH
			ans += tmpH * (i - leftIndex - 1)
		}
		stack = append(stack, i)
	}
	return ans
}

func min(v1, v2 int) int {
	if v1 > v2 {
		return v2
	}
	return v1
}

// 单调栈 递减
// 自定义栈函数实现
func trap2(height []int) int {
	stack := stackDto{}
	ans := 0
	for i, h := range height {
		// 单调递减栈 遇到大元素要出栈；出栈到>=h 还是出栈到 >h 为什么？ 等于h就行了，就可以算面积了
		for !stack.IsEmpty() && height[stack.Peek()] < h {
			top := stack.Pop() //弹出栈顶元素
			if stack.IsEmpty() {
				break //后面没元素了
			}
			leftIndex := stack.Peek() //下一个栈顶
			tmpH := min(h, height[leftIndex]) - height[top]
			ans += (i - leftIndex - 1) * tmpH
		}
		stack.Push(i)
	}
	return ans
}

type stackDto struct {
	db []int
}

// Peek 查看栈顶元素
func (d *stackDto) Peek() int {
	l := len(d.db)
	if l == 0 {
		return 0
	}
	return d.db[l-1]
}

// Pop 弹出栈顶元素
func (d *stackDto) Pop() int {
	l := len(d.db)
	if l == 0 {
		return 0
	}
	v := d.db[l-1]
	d.db = d.db[:l-1]
	return v
}

// IsEmpty 栈是否为空
func (d *stackDto) IsEmpty() bool {
	return 0 == len(d.db)
}

// Push 入栈
func (d *stackDto) Push(val int) {
	d.db = append(d.db, val)
}
